# -*- coding: utf-8 -*-

''' Autor: Neuza Figueira - n.º 6036 '''

from random import uniform
from time import clock
import matplotlib.pyplot as plt
import sys

class QuickSort():
        ''' Class to handle Quicksort implementation and testing.'''
        
        def quick_sort(self, A, p, r):
                '''Python Implementation of Quicksort.'''
                '''@param A -> List to sort.'''
                '''@param p -> First position of the list.'''
                '''@param r -> Last position of the list.'''
                sys.setrecursionlimit(15000) #to avoid errors
                if p < r:
                        q = self.partition(A, p, r)
                        self.quick_sort(A, p, q - 1)
                        self.quick_sort(A, q + 1, r)
                        pass
                return A
                pass


        def partition(self, A, p, r):
                '''Procedute to rearranges the subarray A[p...r] in place.'''
                '''@param A -> Subarray.'''
                '''@param p -> First position of the subarray.'''
                '''@param r -> Last position of the subarray.'''
                x = A[r]
                i = p - 1
                for j in range(p, r):
                        if A[j] <= x:
                                i = i + 1
                                A[i], A[j] = A[j], A[i]
                                pass
                        pass
                A[i + 1], A[r] = A[r], A[i + 1]
                return i + 1
                pass


        def testQuickSort(self):
                '''Testing the complexity of Quicksort.'''
                Z = range(50, 1050, 50)
                T = []
                M = 50
                for n in Z:
                    A = [ uniform(0.0, 1.0) for k in xrange(n)]
                    tempos = []
                    for k in range(M):
                        t1 = clock()
                        self.quick_sort(A, 0, len(A) - 2)
                        t2 = clock()
                        tempos.append(t2-t1)
                    media = reduce(lambda x, y: x + y, tempos) / len(tempos)
                    var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
                    
                    T.append((n,media, var))

                X = [n for n, media, var in T]
                Y = [media for n, media, var in T]
                ct = 45e5
                Z = [(n ** 2) / ct for n, media, var in T]


                plt.grid(True)
                plt.ylabel(u'T(n) - tempo de execução médio em segundos')
                plt.xlabel(u'n - número de elementos')
                plt.plot(X,Y,'rs', label="resultado experimental")
                plt.plot(X, Z, 'b^', label=u"previsão teórica")
                plt.legend()
                plt.show()
                pass
